package com.datastructure;

public class MySequenceArrayMain {
    public static void main(String[] args) {
        MySequenceArray mySequenceArray = new MySequenceArray(10);
        mySequenceArray.insert(10);
        mySequenceArray.insert(1);
        mySequenceArray.insert(55);
        mySequenceArray.insert(3);
        mySequenceArray.forEach();
        mySequenceArray.delete(3);
        mySequenceArray.delete(2);
        mySequenceArray.forEach();
    }
}

/**
 * 有序数组
 */
class MySequenceArray {
    //存储有序数组的集合
    private int[] array;
    //元素数量
    private int size;

    public MySequenceArray(int size) {
        array = new int[size];
        size = 0;
    }

    /**
     * 查找返回下标(二分查找)
     */
    public int find(int value) {
        if (size == 0) {
            return -1;
        }
        int index;
        //当前比对的最大下标
        int maxIndex = size - 1;
        // 当前比对的最小下标
        int minIndex = 0;
        //当前下标
        int currentIndex;
        while (true) {
            if (minIndex > maxIndex) {
                return -1;
            }
            currentIndex = (maxIndex + maxIndex) / 2;
            if (value == array[currentIndex]) {
                return currentIndex;
            } else if (value > array[currentIndex]) {
                minIndex = currentIndex + 1;
            } else {
                maxIndex = currentIndex - 1;
            }
        }
    }

    /**
     * 插入
     */
    public void insert(int value) {
        if (array.length > size) {
            int index;
            for (index = 0; index < size; index++) {
                if (value < array[index]) {
                    //找到了
                    break;
                }
            }
            if (index < size) {
                //数组中存在比value大的数，则index以后的数向后移动一位
                for (int i = size; i > index; i--) {
                    array[i] = array[i - 1];
                }
                //将value插入index处
                array[index] = value;
            } else {
                //最后找不到比value大的数
                array[index] = value;
            }
            size++;
        }
    }

    /**
     * 删除
     */
    public void delete(int value) {
        int index;
        if ((index = find(value)) > -1) {
            for (int i = index; i < size - 1; i++) {
                array[i] = array[i + 1];
            }
            size--;
        }
    }

    /**
     * 遍历
     */
    public void forEach() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}
